package cn.edu.xjtu.剑指offer.exist;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 剑指 Offer 12. 矩阵中的路径
 * <p>
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * <p>
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] arr = {{'a', 'a'}};
        System.out.println(solution.exist(arr, "aaa"));
    }

    boolean result = false;
    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        if ((rows + 1) * (cols + 1) < word.length()) {
            return false;
        }

        char firstChar = word.charAt(0);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == firstChar) {
//                    if (bfs(i, j, rows, cols, board, word)) {
//                        return true;
//                    }
                    if (!result) {
                        visited = new boolean[rows][cols];
                        visited[i][j] = true;
                        dfs(1, i, j, rows, cols, board, word);
                    }
                }
            }
        }
        return result;
    }

    private void dfs(int idx, int row, int col, int rows, int cols, char[][] board, String word) {
        if (idx == word.length()) {
            result = true;
        } else {
            char ch = word.charAt(idx);

            for (int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if (!result && newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol] && board[newRow][newCol] == ch) {
                    visited[newRow][newCol] = true;
                    dfs(idx + 1, newRow, newCol, rows, cols, board, word);
                    visited[newRow][newCol] = false;
                }
            }
        }
    }

    private boolean bfs(int row, int col, int rows, int cols, char[][] board, String word) {
        boolean[][] visited = new boolean[rows][cols];
        Deque<Node> queue = new LinkedList<>();
        queue.addLast(new Node(row, col));
        visited[row][col] = true;
        int idx = 1;
        while (idx != word.length() && queue.size() != 0) {
            Node node = queue.removeFirst();
            boolean flag = false;
            for (int[] direction : directions) {
                int newRow = node.row + direction[0];
                int newCol = node.col + direction[1];
                char ch = word.charAt(idx);
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol] && board[newRow][newCol] == ch) {
                    queue.addLast(new Node(newRow, newCol));
                    visited[newRow][newCol] = true;
                    flag = true;
                }
            }
            if (flag) {
                idx++;
            }
        }
        return idx == word.length();
    }
}

class Node {
    int row;
    int col;

    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
}
